// @algorithm @lc id=53 lang=cpp 
// @title maximum-subarray


// @test([-2,1,-3,4,-1,2,1,-5,4])=6
// @test([1])=1
// @test([5,4,-1,7,8])=23
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        #ifdef USE_PREFIX_SUM
        for(int i=1; i<nums.size(); i++)
            nums[i] += nums[i-1];
        int low = 0, ans = -100000;
        for(auto & preSum : nums){
            ans = max(ans, preSum-low);
            if(preSum < low) low = preSum;
        }
        #else
        int pre = 0, ans = nums[0];
        for(auto & n : nums){
            pre = max(n, n+pre);
            ans = max(ans, pre);
        }
        #endif
        return ans;
    }
};